Deterministic Padded Decompositions and Negative-Weight Shortest Paths
January 28, 2026 (GHC 8102)
A recent breakthrough of Bernstein, Nanongkai, and Wulff-Nilsen established the first near-linear time algorithm for negative-weight single-source shortest paths on integer-weighted graphs. We refine their approach and obtain the first near-linear time *deterministic* algorithm for the problem. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.
The talk will present the entire algorithm and proof at the level of a graduate algorithms class.